package e_ch13_directedG.topoSort;

import java.io.File;
import java.io.IOException;
import java.util.TreeSet;
import java.util.Arrays;
import java.util.Scanner;

/// 无权图(支持有向，无向)
public class Graph implements Cloneable{

    private int V;
    private int E;
    private TreeSet<Integer>[] adj;
    private boolean directed;
    private int[] indegrees, outdegrees;

    public Graph(String filename, boolean directed){

        this.directed = directed;

        File file = new File(filename);

        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be non-negative");
            adj = new TreeSet[V];
            for(int i = 0; i < V; i ++)
                adj[i] = new TreeSet<Integer>();

            indegrees = new int[V];
            outdegrees = new int[V];

            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be non-negative");

            for(int i = 0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                if(a == b) throw new IllegalArgumentException("Self Loop is Detected!");
                if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected!");

                adj[a].add(b);

                if(directed){
                    outdegrees[a] ++;
                    indegrees[b] ++;
                }
                if(!directed)
                    adj[b].add(a);
            }
        }
        catch(IOException e){
            e.printStackTrace();
        }
    }

    public Graph(String filename){
        this(filename, false);
    }

    public boolean isDirected(){
        return directed;
    }

    public void validateVertex(int v){
        if(v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid");
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public boolean hasEdge(int v, int w){
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }

    public Iterable<Integer> adj(int v){
        validateVertex(v);
        return adj[v];
    }

    public int degree(int v){
        if(directed)
            throw new RuntimeException("degree only works in undirected graph.");
        validateVertex(v);
        return adj[v].size();
    }

    public int indegree(int v){
        if(!directed)
            throw new RuntimeException("indegree only works in directed graph.");
        validateVertex(v);
        return indegrees[v];
    }

    public int outdegree(int v){
        if(!directed)
            throw new RuntimeException("outdegree only works in directed graph.");
        validateVertex(v);
        return outdegrees[v];
    }

    public void removeEdge(int v, int w){
        validateVertex(v);
        validateVertex(w);

        if(adj[v].contains(w)){
            E --;

            if(directed){
                indegrees[w] --;
                outdegrees[v] --;
            }
        }

        adj[v].remove(w);
        if(!directed)
            adj[w].remove(v);
    }
    
    public void reverseGraph() { //diy
    	if(!isDirected()) return;
    	
    	TreeSet<Integer>[] reversed = new TreeSet[V];
    	for (int i = 0; i < reversed.length; i++) {
			reversed[i] = new TreeSet<>();
		}
    	
    	for (int v = 0; v < V(); v++) {
    		for (int w : adj(v)) {
				reversed[w].add(v);
			}
		}
    	this.adj =	reversed;    	
	}
    
    public Graph getReversedGraph() {  //diy
    	if(!isDirected()) return this;
    	
    	try {
			Graph shallowCloned = (Graph) super.clone();
			
			TreeSet<Integer>[] reversed = new TreeSet[V];
	    	for (int i = 0; i < reversed.length; i++) {
				reversed[i] = new TreeSet<>();
			}
	    	
	    	for (int v = 0; v < V(); v++) {
	    		for (int w : adj(v)) {
					reversed[w].add(v);
				}
			}
	    	
	    	//变为深克隆
	    	shallowCloned.adj = reversed;   
	    	shallowCloned.indegrees = Arrays.copyOf(outdegrees, V); //入度变出度   出度变入度；
	    	shallowCloned.outdegrees = Arrays.copyOf(indegrees, V);
	    	
	    	return shallowCloned;
	    	
		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
			return null;
		}
    	
	}
    
	@Override
	public Object clone() { // 如果不实现clonable接口，CloneNotSupportedException就会抛出；
		try {
			Graph cloned = (Graph) super.clone(); // super.clone()调用的是native方法  // 返回一个当前对象的浅克隆对象(当前类实现了Clonable接口);

			cloned.adj = new TreeSet[V]; // 对浅克隆进行修改，引用类型的指针指向新空间；

			for (int i = 0; i < adj.length; i++) {
				cloned.adj[i] = new TreeSet<>(); // 对指针开辟空间
				cloned.adj[i].addAll(adj[i]);
			}

			return cloned;

		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
		}

		return null;
	}
	
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();

        sb.append(String.format("V = %d, E = %d, directed = %b\n", V, E, directed));
        for(int v = 0; v < V; v ++){
            sb.append(String.format("%d : ", v));
            for(int w : adj[v])
                sb.append(String.format("%d ", w));
            sb.append('\n');
        }
        return sb.toString();
    }

    
    public static void main(String[] args){

        Graph g = new Graph("ug.txt", true);
        System.out.println(g);
      
//        g.reverseGraph();  //原图reverse
//        System.out.println(g);
        
//        Graph test = (Graph) g.clone();
//        System.out.println(test);
        
        Graph test = g.getReversedGraph(); //返回新的 reversed Graph
        System.out.println(test);
        System.out.println(g);
        
//        g.removeEdge(0, 1);
        for(int v = 0; v < g.V(); v ++)
            System.out.println(g.indegree(v) + " " + g.outdegree(v));
        
        System.out.println();
        
        for(int v = 0; v < test.V(); v ++)
            System.out.println(test.indegree(v) + " " + test.outdegree(v));
        
    }
}
